package com.demo.datastructure.heap;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @description: 2099. 找到和最大的长度为 K 的子序列
 * @author: ljr
 * @create: 2022/1/21 2:57 PM
 */
public class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return null;
        }

        if(k < 1 || k > nums.length){
            return null;
        }

        Heap heap = new Heap(k);

        for(int i = 0;  i < nums.length; i++){
            heap.insert(nums[i], i);
        }
        return heap.getNums();
    }

    public static class Heap{

        private int n = 0;
        private int[][] nums;

        public Heap(int length){
            nums = new int[length][2];
        }

        public void insert(int num, int index){
            if(n == 0){
                nums[n][0] = num;
                nums[n][1] = index;
                n++;
                return;
            }

            if(n == nums.length){
                if(nums[0][0] >= num){
                    return;
                }else{
                    nums[0][0] = nums[--n][0];
                    nums[0][1] = nums[n][1];
                    //向下堆化
                    sink(nums, 0, n-1);
                }
            }

            nums[n][0] = num;
            nums[n][1] = num;
            n++;
            //向上堆化
            swim(nums, n-1, 0);
        }


        private void swim(int[][] nums, int start, int end){
            while(true){
                int min = start;
                if((start - 1) / 2 >= end && nums[(start - 1) / 2][0] > nums[start][0]){
                    min = (start - 1) / 2;
                }
                if(start == min) break;
                swap(nums, start, min);
                start = min;
            }
        }


        private void sink(int[][] nums, int start, int end){
            while(true){
                int max = start;
                if(start * 2 + 1 <= end && nums[start][0] > nums[start * 2 + 1][0]){
                    max = start * 2 + 1;
                }

                if(start * 2 + 2 <= end && nums[max][0] > nums[start * 2 + 2][0]){
                    max = start * 2 + 2;
                }

                if(start == max) break;
                swap(nums, max, start);
                start = max;
            }
        }

        private void swap(int[][] nums, int i, int y){
            int num = nums[i][0];
            int index = nums[i][1];
            nums[i][0] = nums[y][0];
            nums[i][1] = nums[y][1];
            nums[y][0] = num;
            nums[y][1] = index;
        }


        public int getLength(){
            return n;
        }

        public int getNum(){
            return nums[0][0];
        }

        public int[] getNums(){
            if(n == 0){ return null; }
            Arrays.sort(nums, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1] - o2[1];
                }
            });


            int[] newNums = new int[n];
            for(int i = 0; i < n; i++){
                newNums[i] = nums[i][0];
            }
            return newNums;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.maxSubsequence(new int[]{50,75}, 2);
    }

}
